class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        unordered_set<string> st(dictionary.begin(), dictionary.end());
        int n = s.size();
        
        vector<int> memo(n, -1);

        function<int(int)> dfs = [&](int i){
            if(i < 0) return 0;
            int& x = memo[i];
            if(x != -1) return x;

            int res = dfs(i - 1) + 1;
            for(int j = 0; j <= i; ++j)
            {
                if(st.contains(s.substr(j, i - j + 1)))
                {
                    res = min(res, dfs(j - 1));
                }
            }
            return x = res;
        };

        return dfs(n - 1);
    }
};
